public class Qsort {
	// 第一种方式
	public static int partition(Integer[] arr, int low, int high) {
		int x = arr[high];
		int i = low - 1;
		int tmp = 0;
		for (int j = low; j < high; j++) {
			if (x >= arr[j]) {
				i = i + 1;
				tmp = arr[j];
				arr[j] = arr[i];
				arr[i] = tmp;
			}
		}
		tmp = arr[high];
		arr[high] = arr[i+1];
		arr[i+1] = tmp;
		return (i + 1);
	}
	// 第二种方式
	public static int partition1(Integer[] arr, int low, int high) {
		int x = arr[low];
		while (low < high) {
			while (arr[high] >= x && high > low) high--;
			arr[low] = arr[high];
			while (arr[low] <= x && high > low) low++;
			arr[high] = arr[low];
		}
		arr[high] = x;
		return high;
	}
	
	public static void qsort(Integer[] arr, int low, int high) {
		if (low < high) {
			// 每次partition操作得到的位置都是mid最终的位置
			int mid = partition(arr, low, high); 
			qsort(arr, low, mid-1);
			qsort(arr, mid+1, high);
		}		
	}
	
	public static void main(String[] args) {
		Integer[] arr = {2, 4, 1, 8, 3, 7, 5, 6};
		Qsort.qsort(arr, 0, arr.length-1);
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("-%d-", arr[i]);
		}
	}

}